package 蓝桥真题;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class 跳蚱蜢 {
       
	static void swap(int i,int j,char[]chs){
		   char t=chs[i];
		   chs[i]=chs[j];
		   chs[j]=t;
	}
	static int bfs(){
		   String st="432105678";
		   String end="567801234";
		   Map<String,Integer>dp=new HashMap<String,Integer>();
		   Map<String,Integer>dq=new HashMap<String,Integer>();
		   LinkedList<String>q=new LinkedList<String>();
		   LinkedList<String>p=new LinkedList<String>();
		   int di[]={-1,-1,1,2};
		   p.add(st);
		   q.add(end);
		   dp.put(st,0);
		   dq.put(end,0);
		   while(q.size()>0){
			    String pt=p.poll();
			    String qt=q.poll();
			    if(dq.get(pt)!=null)return dp.get(pt)+dq.get(pt);
			    if(dp.get(qt)!=null)return dp.get(qt)+dq.get(qt);
			    int idxp=pt.indexOf('0');
			    int idxq=qt.indexOf('0');
                int pdt=dp.get(pt);
                int qdt=dq.get(qt);
			    for(int i=0;i<4;i++){
			    	int px=((idxp+di[i])%9+9)%9,qx=((idxq+di[i])%9+9)%9;
			    	char[]pchs=pt.toCharArray(),qchs=qt.toCharArray();
			    	swap(px,idxp,pchs);
			    	swap(qx,idxq,qchs);
			    	String pns = String.valueOf(pchs);
			    	String qns = String.valueOf(qchs);
			    	if(dp.get(pns)==null){
			    		dp.put(pns,pdt+1);
			    		p.add(pns);
			    	}
			    	if(dq.get(qns)==null){
			    		dq.put(qns,qdt+1);
			    		q.add(qns);
			    	}
			    }
		   }
		   return -1;
	}
	public static void main(String[] args) {
		   System.out.print(bfs());
	}
}
